package com.zhupf.heap;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2024年11月26日 10:08
 * @Description 295. 数据流的中位数
 * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 * <p>
 * 例如 arr = [2,3,4] 的中位数是 3 。
 * 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
 * 实现 MedianFinder 类:
 * <p>
 * MedianFinder() 初始化 MedianFinder 对象。
 * <p>
 * void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
 * <p>
 * double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
 * <p>
 * 示例 1：
 * <p>
 * 输入
 * ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 * [[], [1], [2], [], [3], []]
 * 输出
 * [null, null, null, 1.5, null, 2.0]
 * <p>
 * 解释
 * MedianFinder medianFinder = new MedianFinder();
 * medianFinder.addNum(1);    // arr = [1]
 * medianFinder.addNum(2);    // arr = [1, 2]
 * medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
 * medianFinder.addNum(3);    // arr[1, 2, 3]
 * medianFinder.findMedian(); // return 2.0
 */
public class MedianFinder {

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(-1);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-3);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-4);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-5);
        System.out.println(medianFinder.findMedian());
    }

    public List<Integer> minHeap;

    public List<Integer> maxHeap;

    private int size;

    public MedianFinder() {
        this.minHeap = new ArrayList<>();
        this.maxHeap = new ArrayList<>();
        minHeap.add(0);
        maxHeap.add(0);
        this.size = 0;
    }

    public void addNum(int num) {
        if (size == 0) {
            maxHeap.add(num);
        } else if (size == 1) {
            if(num<maxHeap.get(1)){
                minHeap.add(maxHeap.get(1));
                maxHeap.set(1,num);
            }else {
                minHeap.add(num);
            }
        } else if (size % 2 == 0) {
            int newNum = Math.max(num, maxHeap.get(1));
            maxHeap.add(Math.min(num, minHeap.get(1)));
            this.maxUp(maxHeap, maxHeap.size() - 1);
            if (newNum > minHeap.get(1)) {
                minHeap.set(1, newNum);
                this.minDown(minHeap, 1);
            }
        } else {
            int newNum = Math.min(num, minHeap.get(1));
            minHeap.add(Math.max(num, maxHeap.get(1)));
            this.minUp(minHeap, minHeap.size() - 1);
            if (newNum < maxHeap.get(1)) {
                maxHeap.set(1, newNum);
                this.maxDown(maxHeap, 1);
            }
        }
        size++;
    }

    public void minDown(List<Integer> minHeap, int parent) {
        while ((parent * 2) < minHeap.size()) {
            int child = parent * 2;
            if (child + 1 < minHeap.size() && minHeap.get(child + 1) < minHeap.get(child)) {
                child = child + 1;
            }
            if (minHeap.get(parent) > minHeap.get(child)) {
                int tmp = minHeap.get(parent);
                minHeap.set(parent, minHeap.get(child));
                minHeap.set(child, tmp);
            } else {
                break;
            }
            parent = child;
        }
    }

    public void minUp(List<Integer> minHeap, int child) {
        while (child > 1) {
            int parent = child / 2;
            if (minHeap.get(child) < minHeap.get(parent)) {
                int tmp = minHeap.get(parent);
                minHeap.set(parent, minHeap.get(child));
                minHeap.set(child, tmp);
            } else {
                break;
            }
            child = parent;
        }
    }

    public void maxDown(List<Integer> maxHeap, int parent) {
        while ((parent * 2) < maxHeap.size()) {
            int child = parent * 2;
            if (child + 1 < maxHeap.size() && maxHeap.get(child + 1) > maxHeap.get(child)) {
                child = child + 1;
            }
            if (maxHeap.get(parent) < maxHeap.get(child)) {
                int tmp = maxHeap.get(parent);
                maxHeap.set(parent, maxHeap.get(child));
                maxHeap.set(child, tmp);
            } else {
                break;
            }
            parent = child;
        }
    }

    public void maxUp(List<Integer> maxHeap, int child) {
        while (child > 1) {
            int parent = child / 2;
            if (maxHeap.get(child) > maxHeap.get(parent)) {
                int tmp = maxHeap.get(parent);
                maxHeap.set(parent, maxHeap.get(child));
                maxHeap.set(child, tmp);
            } else {
                break;
            }
            child = parent;
        }
    }

    public double findMedian() {
        if (size % 2 == 0) {
            return (minHeap.get(1) + maxHeap.get(1)) / 2.0;
        } else {
            return (double) maxHeap.get(1);
        }
    }


}
